1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120
| #include <bits/stdc++.h> #define eb emplace_back using namespace std; using ll = long long; using ull = unsigned long long; mt19937 mt(random_device{}()); int t, n, m; int u, v; ll a, b; ll ans; vector<int> gra[45], gb[45], tr[45], rt; bool vb[45]; int del[45]; void dfs20(int u) { if (u > n) { int tp = 0; memset(vb, 0, sizeof(vb)); for (int i = 1; i <= n; ++i) { if (!del[i]) continue; ++tp; for (auto &j : gb[i]) { vb[j] = 1; } } int tot = 0; for (int j = 0; j < m; ++j) tot += vb[j]; ans = min(ans, b * tp + a * (m - tot)); return; } del[u] = 0; dfs20(u + 1); del[u] = 1; dfs20(u + 1); } vector <int> hb[2]; int ddd[45], ttt, siz[45]; void js(int u, int v) { vb[u] = 1; ddd[u] = ++ttt; siz[u] = 1; for (auto &i : gra[u]) { if (i == v) continue; if (vb[i]) { if (ddd[i] >= ddd[u]) { hb[0].eb(i); hb[1].eb(u); } continue; } tr[u].eb(i); js(i, u); siz[u] += siz[i]; } } ll f[45][2]; void dp(int u) { f[u][0] = b; f[u][1] = a * del[u]; for (auto &i : tr[u]) { dp(i); f[u][0] += min(f[i][0], f[i][1]); f[u][1] += min(f[i][0], f[i][1] + a); } } void dfsplus(int step) { if ((ull)step == hb[0].size()) { ll tot = 0; for (auto &i : rt) { dp(i); tot += min(f[i][0], f[i][1]); } ans = min(ans, tot); return; }
++del[hb[0][step]]; dfsplus(step + 1); --del[hb[0][step]];
if (hb[1][step] != hb[0][step]) { ++del[hb[1][step]]; dfsplus(step + 1); --del[hb[1][step]]; } } int main() { freopen("random.in", "r", stdin); freopen("random.out", "w", stdout); scanf("%d", &t); while (t--) { ans = 1e18; ttt = 0; scanf("%d%d%lld%lld", &n, &m, &a, &b); for (int i = 1; i <= n; ++i) gra[i].clear(), gb[i].clear(), tr[i].clear(); hb[0].clear(); hb[1].clear(); for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); gra[u].eb(v); if (u != v) gra[v].eb(u); gb[u].eb(i); if (u != v)gb[v].eb(i); } if (n <= 20) { dfs20(1); printf("%lld\n", ans); } else { memset(vb, 0, sizeof(vb)); memset(del, 0, sizeof(del)); rt.clear(); for (int i = 1; i <= n; ++i) { if (!vb[i]) js(i, 0), rt.eb(i); } dfsplus(0); printf("%lld\n", ans); } } return 0; }
|